/**
 * @author : cyb1010
 * @date   : 2024-12-04 12:28:26
 * @file   : oi.cpp
 */
#include <bits/stdc++.h>
using namespace std;
#define fo(s) freopen(s ".in", "r", stdin), freopen(s ".out", "w", stdout)
#define fi first
#define se second
#define ALL(v) (v).begin(), (v).end()
#define SZ(v) int(v.size())
typedef double db;
typedef long double ldb;
typedef long long ll;
typedef unsigned long long ull;
void ckmx(int &x, int y) { x < y && (x = y); }
void ckmn(int &x, int y) { x > y && (x = y); }
const int N = 2010;
int __, ID, _, n, m, mn;
vector<int> g[N];

void solve1(int x) {
    queue<int> q;
    vector<int> dep(n + 1), frm(n + 1);
    fill(ALL(dep), N), dep[x] = 0, q.push(x);
    while (!q.empty()) {
        int p = q.front();
        q.pop();
        for (int i : g[p]) {
            if (i == frm[p]) continue;
            if (i == x) return ckmn(mn, dep[p] + 1);
            if (dep[i] > dep[p] + 1)
                dep[i] = dep[p] + 1, q.push(i), frm[i] = p;
            else
                ckmn(mn, dep[p] + dep[i] + 1);
        }
    }
}

void work() {
    cin >> n >> m, mn = N;
    for (int i = 1; i <= n; i++) g[i].clear();
    for (int x, y, i = 1; i <= m; i++)
        cin >> x >> y, g[x].push_back(y), g[y].push_back(x);
    for (int i = 1; i <= n; i++) solve1(i);
    cout << -mn - m + 2 << ' ' << "0\n";
}
int main() {
    fo("oi");
    cin.tie(0)->sync_with_stdio(0);
    cin >> ID >> _;
    while (_--) work();
    return 0 ^ __ ^ 0;
}